An error-correction code is a method of coding information messages in a manner that incorporates redundancy. By exploiting this redundancy, a decoder for an error-correcting code is able to provide error-correcting functionality. Of course, redundancy as incorporated within error-correction codes does not necessarily imply an exact duplication of data.
Herein, the term error-correction code (or code), is a mapping of information messages to codewords, each codeword being an ordered collection of symbols from some finite symbol set. Each codeword of a code has the same codeword length. The codeword length is the number of symbols in a codeword. The codeword length may be infinite. A symbol set is a collection of distinct identifiers, such as {0 1} or {1 .beta..beta..sup.2 .beta..sup.3 }. The codewords of a code form a proper subset of all possible ordered collections of symbols from the symbol set--the collections of a size equal to the codeword length. Some ordered collections of symbols from the symbol set are codewords of the code, and others are not, and this is what provides the required redundancy.
Typically, a set of constraints determines which ordered collections of symbols are codewords of a code and which are not. The constraints are expressed in terms of one or more operators that are associated with the symbol set. Highly structured constraints are usually desirable to enable simple encoding and decoding of a code. The constraints are usually defined over groups or fields, which have well-known mathematical properties.
A code where the information message is part of the codeword itself is called a systematic code. That is, with a systematic code, the information messages are expressed in terms of the same symbol set used for the codewords themselves, and the symbols of the information message appear within the associated codeword, in some arbitrary but fixed placement pattern.
A code with a finite codeword length is called a block code.
A cyclic code is a code where any cyclic shift of a codeword is also a codeword. A cyclic code, however, is not limited to block codes.
A quasi-cyclic code is a code where some, but not all, cyclic shifts of a codeword are codewords. An example of a quasi-cyclic code is a tail-biting block convolutional code. Such a code is well known in the art. Techniques used with cyclic codes are often applicable to quasi-cyclic codes as long as the distinction therebetween is accounted for.
A binary code is a code having symbols that are bits (i.e. 0 and 1).
A product code is a code constructed from two or more codes, called component codes of the product code, which are combined in an orthogonal manner. Specifically, an N-dimensional product code is a code composed of N component codes, where each codeword of the product code can be represented as an N-dimensional array of symbols such that, for any selected dimension and any set of valid indices for other dimensions, the ordered collection of symbols determined by moving along the selected dimension while keeping the indices of the other dimensions fixed, is a codeword of the component code associated with the selected dimension. Note that a component code of a product code may itself be a product code.
Parity is a well known method of coding. Using "even-parity" with bits a constraint exists that a set of symbols sums modulo-2 to 0. For example, a set of message information bits {1 0} are encoded as the codeword {1 0 1}; a set of message information bits {1 1} are encoded as the codeword {1 1 0}. Parity is well known in the art. As a simple example of a product code, consider a two-dimensional binary product code where each of two component codes are "even-parity" codes with a codeword length of 3. The following collection of bits is a valid codeword for such a product code:
1 0 1
0 1 1
1 1 0
Observe that each row and each column has even parity. This product code has only 16 distinct codewords. Each codeword has a codeword length of 9. It is apparent that without constraints, there are 2.sup.9 (512) possible ordered collections of bits of length 9.
In order to improve error correcting capability of existing product codes, further dimensions are added to the product code. For example, the two-dimensional product code shown above has a minimum Hamming distance of 4--a minimum of 4 bits must be flipped within a product codeword to produce another valid product codeword. By adding a third dimension of even-parity encoding with codeword length of 3, the minimum Hamming distance is increased to 8. This larger Hamming distance is indicative of more powerful error-correcting capabilities; however, in order to achieve this increased error-correcting capability, 19 of 27 bits within the product codeword are devoted to parity information. In the two-dimensional product code shown above, nearly half the bits are information, whereas in the three-dimensional product code, less than 1/3 of the bits is information bits. In this example, the percentage of information bits within a codeword drops significantly when an additional dimension is added to the product code. In order to increase this percentage, an increased amount of information bits is required; this is also a significant limitation.